import sun.reflect.generics.tree.Tree;

import java.util.*;

class NumArray {
    class TreeNode{
        int sum;
        int start;
        int end;
        TreeNode left;
        TreeNode right;

        public TreeNode(int sum, int start, int end){
            this.sum = sum;
            this.start = start;
            this.end = end;
        }
    }

    TreeNode root;

    private int getNodeMid(TreeNode node){
        return node.start + (node.end - node.start) / 2;
    }

    private int[] getPrefixArr(int[] nums){
        int[] prefixArr = new int[nums.length];
        int tmpSum = 0;
        for(int i = 0; i < nums.length; i++){
            tmpSum += nums[i];
            prefixArr[i] = tmpSum;
        }
        return prefixArr;
    }

    private int prefixGetRangeSum(int[] prefixArr, int start, int end){
        return prefixArr[end] - (start == 0 ? 0 : prefixArr[start - 1]);
    }

    private TreeNode buildAndGetRoot(int[] prefixArr){
        Queue<TreeNode> buildQueue = new LinkedList<>();
        TreeNode root = new TreeNode(prefixArr[prefixArr.length - 1], 0, prefixArr.length - 1);
        buildQueue.add(root);
        while(!buildQueue.isEmpty()){
            TreeNode tmpNode = buildQueue.poll();
            if(tmpNode.start == tmpNode.end){ continue; }
            int mid = getNodeMid(tmpNode);
            TreeNode left = new TreeNode(prefixGetRangeSum(prefixArr, tmpNode.start, mid), tmpNode.start, mid);
            TreeNode right = new TreeNode(prefixGetRangeSum(prefixArr, mid + 1, tmpNode.end), mid + 1, tmpNode.end);
            tmpNode.left = left; tmpNode.right = right;
            buildQueue.add(left); buildQueue.add(right);
        }
        return root;
    }

    private int travelUpdateSum(TreeNode tmpNode, int index, int val){
        if(tmpNode.start == tmpNode.end){
            int oldVal = tmpNode.sum;
            tmpNode.sum = val;
            return oldVal;
        }
        TreeNode leftNode = tmpNode.left, rightNode = tmpNode.right;
        int oldVal;
        if(leftNode != null && index <= leftNode.end){
            oldVal = travelUpdateSum(leftNode, index, val);
        }
        else {
            oldVal = travelUpdateSum(rightNode, index, val);
        }
        tmpNode.sum += val - oldVal;
        return oldVal;
    }

    private int travelGetRangeSum(TreeNode tmpNode, int start, int end){
        if(tmpNode.start == start && tmpNode.end == end) {
            return tmpNode.sum;
        }
        int mid = getNodeMid(tmpNode);
        if(end <= mid){
            return travelGetRangeSum(tmpNode.left, start, end);
        }
        else if(mid + 1 <= start){
            return travelGetRangeSum(tmpNode.right, start, end);
        }
        else{
            return travelGetRangeSum(tmpNode.left, start, mid) + travelGetRangeSum(tmpNode.right, mid + 1, end);
        }
    }


    public NumArray(int[] nums) {
        this.root = buildAndGetRoot(getPrefixArr(nums));
    }

    public void update(int index, int val) {
        travelUpdateSum(root, index, val);
    }

    public int sumRange(int left, int right) {
        return travelGetRangeSum(root, left, right);
    }
}
